package list;

/**
 * 双向循环列表
 *
 * @param <E> 要添加的元素
 */
public class LinkedList<E> {
    //head用来寻访头结点的引用
    private Node head;
    //size用于存放链表的长度(或者说)
    private int size;

    /**
     * Node类用来描述链表中的一个节点
     * 其中,data用于存放元素,next和prev
     * 分别存放该节点的后续节点和前驱节点的引用.
     */
    class Node {
        E data;
        Node next;
        Node prev;

        Node(E e) {
            data = e;
        }
    }

    /**
     * 将元素添加到链表的末尾
     *
     * @param e 要添加的元素
     * @return 添加成功, 返回true
     */
    public boolean add(E e) {
        //将元素封装成节点
        Node node = new Node(e);
        //如果链表为空,则新节点成为头节点
        if (head == null) {
            head = node;
            head.next = head;
            head.prev = head;
            //将链表的长度加1
            size++;
            return true;
        }
        //找到尾节点
        Node last = head.prev;
        //将新节点添加到尾节点后面
        last.next = node;
        node.next = head;
        head.prev = node;
        node.prev = last;
        //将链表的长度加1
        size++;
        return true;
    }

    @Override
    public String toString() {
        if (head == null) {
            //如果链表为空,则返回"[]";
            return "[]";
        }
        //如果链表不为空则遍历各个节点
        StringBuilder sb = new StringBuilder("[");
        //把根元素添加到StringBuilder里面
        sb.append(head.data);
        //获得根节点的下一个节点
        Node next = head.next;
        //如果某个节点的下一个节点正好是根节点,则遍历结束
        while (next != head) {
            //将当前节点的元素添加到StringBuilder里面
            sb.append("," + next.data);
            //获得当前节点的下一个节点
            next = next.next;
        }
        return sb.append("]").toString();

    }

    /**
     * 获得链表的长度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 获得指定位置(下标)处的元素
     * @param index  下标(小标从0开始)
     * @return  该位置对应的元素
     */
    public E get(int index){
        //如果下标在合理的范围之内,直接抛出异常即可.
        if (index<0||index>=size){
            throw  new IndexOutOfBoundsException("下标越界");
        }
        Node node = getNode(index);
        //返回该节点的元素
        return node.data;
    }

    private Node getNode(int index) {
        //从头节点开始遍历
        Node node=head;
        //如果index小于链表长度的一半,则可以顺时针遍历(也就是通过next属性来获得下一个节点)
        //>>移位运算相当于size/2
        if (index<size>>1){
            for (int i=0;i<index;i++){
                node=node.next;
            }
        }else {
            //如果index大于活着等于链表长度的一半,则逆时针遍历
            for (int i=size;i>index;i--){
                node=node.prev;
            }
        }
        return node;
    }

    /**
     * 删除指定位置处的元素
     * @param index  指定位置
     * @return       被删除的元素
     */
    public E remove(int index){
        if (index<0||index>=size){
            throw new IndexOutOfBoundsException("下标越界");
        }
        //如果列表的长度为1,则删除该节点之后,需要将head设置为null.
        if (size==1){
            E e=head.data;
            head=null;
            size--;
            return e;
        }
        //找到要删除的节点
        Node node=getNode(index);
        //找到该节点的上一个节点和下一个节点
        Node next=node.next;
        Node prev=node.prev;
        //上一个节点和下一个节点之间建立引用关系(相当于删除了node这个节点)
        next.prev=prev;
        prev.next=next;
        //如果删除的是头节点,则其下一个节点成为头节点
        if (index==0){
            head=next;
        }
        size--;
        return node.data;
    }
    //将元素添加到指的位置
    public void add(int index,E e){
        if (index<0||index>size){
            throw new IndexOutOfBoundsException("下标越界");
            }
        //index等于size,等价于追加元素
        if (index==size){
            add(e);
            return;
        }
        //将元素封装节点
        Node node=new Node(e);
        //找到下标等于index节点(该节点会成为新插入节点的下一个节点)
        Node next=getNode(index);
        //找到next节点的上一个节点(该节点会成为新插入节点的上一个节点)
        Node prev=next.prev;
        //将node放在next和prev之间
        next.prev=node;
        node.prev=prev;
        prev.next=node;
        node.next=next;
        //如果index等于0,则新添加的节点成为头节点
        if (index==0){
            head=node;
        }
        size++;


    }

}
